『Regular-expression derivatives reexamined』

OWENS S, REPPY J, TURON A. Regular-expression derivatives re-examined. Journal of Functional Programming. 2009;19(2):173-190. doi:10.1017/S0956796808007090

Regular-expression derivatives re-examined | Journal of Functional Programming | Cambridge Core

(PDF)

1. どんなもの？

忘れ去られていたらしい正規表現導分(?)(RE derivatives)についてまとめたもの。

Brzozowski derivative(ゾゾウスキ導分)

2. 先行研究と比べてどこがすごい？

正規表現をきちんと形式化した？

3. 技術や手法のキモはどこ？

正規表現から決定性有限オートマトン(DFA)への変換アルゴリズム

4. どうやって有効だと検証した？

PLT Scheme、Standard MLのそれぞれでスキャナジェネレータなるものを実装

5. 議論はある？

Unicodeのような大規模文字セットのサポート

6. 次に読むべき論文は？

ml-ulex

$ \sum : シンボル、有限のアルファベット文字列

$ \sum * : すべての有限文字列

$ ε : 空文字列

$ \mathcal{L} : language、$ \mathcal{L} \subseteq \sum *

引用

Aho, Alfred V., & Ullman, Jeffrey D. (1972). 『The Theory of Parsing, Translation, and Compiling』. Vol. 1. Englewood Cliffs, NJ: Prentice-Hall.

Aho, Alfred V., Hopcroft, John E., & Ullman, Jeffrey D. (1974). 『The Design and Analysis of Computer Algorithms. Reading』, MA: Addison Wesley.

Aho, Alfred V., Sethi, Ravi, & Ullman, Jeffry D. (1986). 『Compilers: Principles』, Techniques, and Tools. Reading, MA: Addison Wesley.

Appel, Andrew W. (1998). 『Modern Compiler Implementation in ML. Cambridge, UK: Cambridge University Press』. Appel, Andrew W., Mattson, James S., & Tarditi, David R. 1994 (Oct.). A lexical analyzer generator for Standard ML. Available from http://smlnj.org/doc/ML-Lex/manual.html.

Baxter, Ira, Pidgeon, Christopher, & Mehlich, Michael. (2004). 『DMS: Program transformations for practical scalable software evolution』. International Conference on Software Engineering.

Berry, G ́ erard. (1999). 『The Esterel v5 Language Primer Version 5.21 release 2.0』. ftp:// ftp-sop.inria.fr/meije/esterel/papers/primer.pdf.

Berry, G ́ erard, & Sethi, Ravi. (1986). 『From regular expressions to deterministic automata』. Theoretical Compter Science, Dec., 117–126.

Brzozowski, Janusz A. (1964). 『Derivatives of Regular Expressions』. Journal of the ACM, 11(4), 481494.

English, Joe. (1999). 『How to validate XML』. http://www.flightlab.com/~joe/sgml/ validate.html. Findler, Robert Bruce, Clements, John, Flanagan, Cormac, Flatt, Matthew, Krishnamurthi, Shriram, Steckler, Paul, & Felleisen, Matthias. (2002). DrScheme: 『A programming environment for Scheme』. Journal of Functional Programming, 12(2), 159–182.

Fisher, Charles N., & LeBlanc, Jr., Richard J. (1988). 『Crafting a Compiler』. Menlo Park, CA: Benjamin/Cummings.

McNaughton, R., & Yamada, H. (1960). Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9, 39–47.

Rabin, M. O., & Scott, D. (1959). 『Finite automata and their decision problems』. IBM Journal of Research and Development, 3(2), 114–125.

Schmidt, Martin. (2002). 『Design and Implementation of a Validating XML Parser in Haskell』. Masters thesis, University of Applied Sciences Wedel, Computer Science Department.

Sen, Koushik, & Ros ̧u, Grigore. (2003). 『Generating optimal monitors for extended regular expressions』. Proceedings of runtime verification (RV’03). Electronic Notes in Theoretical Computer Science, vol. 89, no. 2. Elsevier Science.

Thompson, Ken. (1968). 『Regular expression search algorithm』. Communications of the ACM, 11(6), 419–422.

Unicode Consortium. (2003). 『The Unicode Standard, Version 4』. Reading, MA: Addison-Wesley Professional. Findler, Robert Bruce, Clements, John, Flanagan, Cormac, Flatt, Matthew, Krishnamurthi, Shriram, Steckler, Paul, & Felleisen, Matthias. (2002). 『DrScheme: A programming environment for Scheme』. Journal of Functional Programming, 12(2), 159–182.

確認用